package 动态规划;

/**
 * 198. 打家劫舍
 * 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
 * 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
 *
 * 解题思路;
 *  这道题可以使用DP动态规划来实现，动态规划的核心思想是将大问题分解为小问题，并利用子问题的解来构建原问题的解。
 *  1：状态定义： 定义dp[i]表示前i个房屋所能得到的最高金额。
 *  2：状态转移方程：对于第 i 个房屋，有两种选择：
 *      - 偷当前房屋：此时无法偷取前一个房屋，只能偷前前一个房屋，所以dp [i] = dp[i-2] + nums[i];
 *      - 不偷当前房屋：此时可以偷取前一个房屋,所以 dp[i] = dp[i-1] ;
 *     总结：dp[i] 为上述两个选择的较大值，所以dp[i] = max(dp[i-2] + nums[i],dp[i-1])
 *  3:初始条件：
 *      如果只有1个房屋：那么 dp[0] = nums[0]
 *      如果有两个房屋： dp[1] = max(nums[0],nums[1]) // 只能偷其中一个较大的值
 *
 *      接下来编写代码即可
 *
 */
public class L_198 {
    public int rob(int[] nums) {
        if (nums.length == 0){
            return -1;
        }
        // 定义动态数组dp
        int[] dp =new int[nums.length+1];
        if (nums.length == 1){
            return nums[0];
        }else if (nums.length == 2){ // 如果只有两个房屋，那么只能偷其中一个
            return Math.max(nums[0],nums[1]);
        }else {
            dp[0] = nums[0]; // 0 为第一个房屋
            dp[1] = Math.max(nums[0],nums[1]);
            for (int i = 2; i < nums.length ; i++) {
                dp[i] = Math.max(dp[i-2]+nums[i],dp[i-1]);
            }
        }
        return dp[nums.length-1];
    }
}
